home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / scope / 076-100 / scopedisk81 / wkeys / msort.c < prev    next >
C/C++ Source or Header  |  1995-03-19  |  11KB  |  290 lines
  1. /*
  2.  *  MSORT.C             version 1.0             18-Nov-1986
  3.  *
  4.  *  A general-purpose implementation of a merge-sort for linked lists.
  5.  *
  6.  *  Written for the Commodore Amiga 1000, version 1.1
  7.  *  using Lattice C v3.03 by Davide P. Cervone
  8.  *
  9.  *  The merge-sort algorithm takes advantage of the fact that it is
  10.  *  easy to combine two sorted lists into one sorted list:  just keep
  11.  *  taking the smaller item off the top of the two lists and add it
  12.  *  to the bottom of the new list until the original lists are empty.
  13.  *
  14.  *  The sort algorithm first places each item to be sorted in its
  15.  *  own list (one item long).  Pairs of these singleton lists are merged
  16.  *  in the manner described above, and we are left with half as many lists
  17.  *  as before, each two items long.  Pairs of these lists are combined to
  18.  *  form half as many lists again, each four items long.  This process is 
  19.  *  repeated until only one list remains.  This is the final, sorted list.
  20.  *
  21.  *  The merge-sort is ideal for linked lists, since it does not require
  22.  *  random access look-ups (which are difficult in linked-lists).  It does 
  23.  *  not require extra "work-space", so no memory is wasted.  Finally, its 
  24.  *  result is a simple, linked-list structure, ready to use (unlike some sort 
  25.  *  methods that result in trees or other structures were it is dificult to 
  26.  *  get from one item to the next).
  27.  *
  28.  *  The merge-sort is fairly efficient.  In it's worst case, it takes
  29.  *  n * (log(n) - 1) + 1 comparisons to sort  n  items (where the log() 
  30.  *  function is the log to base 2).  Thus, for 1024 items, the maximum 
  31.  *  number of comparisons is 1024*(10-1)+1 = 9217, or approximately 9
  32.  *  comparisons per item.  And that's its worst case!  Compare this to
  33.  *  a worst case of n*(n-1)/2 for some popular sorts (e.g., the tree sort).  
  34.  *  The worst case for the tree sort for 1024 items is 523776 compares!
  35.  *
  36.  *  In its best case, the merge-sort takes  n * log(n) / 2  comparisons.
  37.  *  For our example of n=1024, that's 5120 comparisons.  For the tree sort,
  38.  *  the minimum is approximately  n * (log(n) - 2)  comparisons, for a 
  39.  *  minimum of 8192 comparisons for 1024 items. 
  40.  *
  41.  *  Note that the maximum comparisons that will ever occur with the merge-sort 
  42.  *  is no more than  n  more than the minimum number possible with the tree 
  43.  *  sort.  
  44.  *
  45.  *  While these numbers look impressive, there is one drawback:  the merge-
  46.  *  sort is heavily weighted toward its worst case, since the merge sort skips 
  47.  *  comparisons only when one list runs out of items more than one item before 
  48.  *  the other.  In practice, the average number of comparisons made by the 
  49.  *  merge-sort is a consistant 96% of the maximum number.  This gives you a very
  50.  *  acurate estimate of the number of comparisons (hence the time it takes) to 
  51.  *  sort a list of a particular size.  Since the maximum value is so close to
  52.  *  the most probable value, you don't have to worry about pathelogic cases
  53.  *  slowing down your sort routine (for a tree sort, the "pathelogic" case
  54.  *  is a pre-sorted list, which may not be an uncommon case).
  55.  *
  56.  *  In a comparison against the tree sort using random data (the kind the 
  57.  *  tree sort handles best), the merge-sort was found to take 96% of its 
  58.  *  maximum number of sorts, while the tree sort averaged about 38% more than
  59.  *  it's minimum (there was considerably more variation with the tree sort).
  60.  *  Overall, the tree sort was found to take a consitant 25% more comparisons
  61.  *  than the merge-sort on lists of length 300 items to 10000 items.  For
  62.  *  100 items, the difference drops off to about 15%, and for 10 items, the two
  63.  *  sorts are about the same, with the merge-sort comming out a little bit
  64.  *  ahead (one or two comparisons out of an average of 23).
  65.  *
  66.  *  All in all, the merge-sort is an effective, fast, and very useful sort
  67.  *  that compares favorably with other sort algorithms.
  68.  */
  69.  
  70. #include <exec/types.h>
  71.  
  72. #define ADD_TO_NEWLIST(l)   (newlist = (newlist->Next = l))
  73.  
  74. /*
  75.  *  The linked list is a double-linked list (there are pointers to both
  76.  *  the previous and the following item).  The end of the list is marked
  77.  *  by NULL pointers.
  78.  *
  79.  *  The pointers should appear at the top of the structure you intend to
  80.  *  sort, so if you are sorting a linked list of people's names, you might
  81.  *  use a structure like the following in your main program:
  82.  *
  83.  *      struct ListItem
  84.  *      {
  85.  *          struct ListItem *Next;
  86.  *          struct ListItem *Prev;
  87.  *          char FirstName[30];
  88.  *          char MiddleInitial;
  89.  *          char LastName[50]
  90.  *      };
  91.  *
  92.  *  The pointers must be the first fields so that mSort() and Merge() can
  93.  *  find the pointers without having to know anything about the structure
  94.  *  of the data you are sorting.
  95.  */
  96.  
  97. /*
  98.  *  The #ifndef is so that this module can be #included into the program
  99.  *  that calls mSort(), rather than requiring it to be linked in separately.
  100.  *  To avoid a conflicting definition error, #define NextList to be the
  101.  *  name of the pointer to the previous item as it is declared in your
  102.  *  program (for the example given above, user #define NextList Prev).
  103.  *  be sure that the #define and the struct ListItem declaration both
  104.  *  appear before the #include for this module
  105.  */
  106.  
  107. #ifndef NextList
  108. struct ListItem
  109. {
  110.    struct ListItem *Next;
  111.    struct ListItem *NextList;
  112. };
  113. #endif
  114.  
  115. /*
  116.  *  These are the compare and dispose functions passed to mSort() (see
  117.  *  mSort() for more details), and are assigned to global variables so that
  118.  *  they don't have to be passed to mMerge() every time it is called.
  119.  */
  120.  
  121. static int  (*mCompare)() = NULL;
  122. static void (*mDispose)() = NULL;
  123.  
  124. /*
  125.  * mMerge()
  126.  *
  127.  *  combines two sorted linked lists into one sorted linked list, using
  128.  *  the mCompare() function to determine the sorting, and the dispose()
  129.  *  function to remove duplicate values.
  130.  *
  131.  *      list1           a pointer to the first linked list
  132.  *      list2           a pointer to the second linked list
  133.  */
  134.  
  135. struct ListItem *
  136. mMerge(list1,list2)
  137. struct ListItem *list1, *list2;
  138. {
  139.    static struct ListItem top_item;
  140.    static struct ListItem *newlist, *temp;
  141.    static int result;
  142.  
  143.    top_item.Next = top_item.NextList = NULL;
  144.    newlist = &top_item;
  145.  
  146. /*
  147.  *  While there are still items in each list, compare the top items in the 
  148.  *  lists.  Link the smaller one to the end of the new, combined list, and
  149.  *  pop the item off the top of the old list.  If the top items are equal, 
  150.  *  then add one of them to the new list, and if there is a dispose function,
  151.  *  get rid of the other one, otherwise add the second one into the list
  152.  *  as well.
  153.  *
  154.  *  When one of the lists is exauseted, add any remaining items from 
  155.  *  the other list onto the end of the result list, and return a pointer
  156.  *  to the final, sorted list.
  157.  */
  158.  
  159.    while (list1 != NULL && list2 != NULL)
  160.    {
  161.       result = (*mCompare)(list1,list2);
  162.       if (result < 0)
  163.       {
  164.          ADD_TO_NEWLIST(list1);
  165.          list1 = list1->Next;
  166.       }
  167.       else if (result > 0)
  168.       {
  169.          ADD_TO_NEWLIST(list2);
  170.          list2 = list2->Next;
  171.       }
  172.       else
  173.       {
  174.          ADD_TO_NEWLIST(list1);
  175.          list1 = list1->Next;
  176.          if (mDispose == NULL)
  177.          {
  178.             ADD_TO_NEWLIST(list2);
  179.             list2 = list2->Next;
  180.          } else {
  181.             temp = list2;
  182.             list2 = list2->Next;
  183.             temp->Next = temp->NextList = NULL;
  184.             (*mDispose)(temp);
  185.          }
  186.       }
  187.    }
  188.    if (list1 != NULL) ADD_TO_NEWLIST(list1);
  189.    else if (list2 != NULL) ADD_TO_NEWLIST(list2);
  190.    return(top_item.Next);
  191. }
  192.  
  193. /*
  194.  *  mSort()
  195.  *
  196.  *  sorts a linked list of items of any sort, using a user-provided comparison
  197.  *  routine.  Duplicate items will be removed if the dispose routine is
  198.  *  provided.  The result list will be a doubly-linked list (pointers go both
  199.  *  forward and backward) that is sorted.  mSort() returns a pointer to
  200.  *  the top of the result list.
  201.  *
  202.  *      cur_item        a pointer to the begining of the original, unsorted
  203.  *                      list.
  204.  *      compare()       a pointer to a function that compares two
  205.  *                      ListItems and returns a negative number if
  206.  *                      the first item is smaller, zero if they are
  207.  *                      equal, and a positive number if the first
  208.  *                      item is larger than the second.  Compare() 
  209.  *                      should take two parameters, the pointers
  210.  *                      to the ListItems that are to be compared.
  211.  *      dispose()       disposes of a duplicate ListItem.  Dispose()
  212.  *                      should accept one parameter, the pointer to
  213.  *                      the ListItem to be removed.  Dispose() should
  214.  *                      free any memory allocated to the ListItem.
  215.  *                      This list item will not appear in the final
  216.  *                      linked list.  If dispose in NULL, then 
  217.  *                      duplicate items are retained in the list.
  218.  */
  219.  
  220. struct ListItem *
  221. mSort(cur_item,compare,dispose)
  222. struct ListItem *cur_item;
  223. int (*compare)();
  224. void (*dispose)();
  225. {
  226.    static struct ListItem *first_item, *next_item;
  227.    
  228. /*
  229.  *  Put the compare and dispose routines where mMerge() can find them
  230.  */
  231.    mCompare = compare;
  232.    mDispose = dispose;
  233.  
  234.    first_item = NULL;
  235.    if (cur_item != NULL)
  236.    {
  237. /*
  238.  *  Put each item in the original list into a separate list.  Use the
  239.  *  NextList field to link the individual lists into a list (a linked list
  240.  *  of linked lists).  Link the end of the list to the begining so we get
  241.  *  a ring rather than a list.
  242.  */
  243.       first_item = cur_item;
  244.       do
  245.       {
  246.          next_item = cur_item->Next;
  247.          cur_item->Next = NULL;
  248.          cur_item->NextList = (next_item != NULL)? next_item : first_item;
  249.          cur_item = next_item;
  250.       } while (cur_item != NULL);
  251. /*
  252.  *  While there's more than one list left in the ring (i.e., the list 
  253.  *  following the current one is not itself), then merge the current list
  254.  *  with the one following it (keep track of the first list after the ones
  255.  *  we're combining so we can link the result of the merge back into
  256.  *  the ring).  Finally, if there were more than two lists in the ring
  257.  *  (i.e., if the current list is neither equal to the one preceding it nor
  258.  *  equal to the one after the list with which it was combined), then 
  259.  *  link the result list into the ring, otherwise link the result list
  260.  *  to itself (since there were only two lists in the ring, their
  261.  *  merger should leave us with only one).  Move down the ring, so we
  262.  *  can merge the next two lists in the ring.
  263.  */
  264.       while ((cur_item = first_item->NextList) != first_item)
  265.       {
  266.          next_item = cur_item->NextList->NextList;
  267.          cur_item = mMerge(cur_item,cur_item->NextList,compare,dispose);
  268.          if (cur_item == first_item || cur_item == next_item)
  269.          {
  270.             cur_item->NextList = cur_item;
  271.          } else {
  272.             first_item->NextList = cur_item;
  273.             cur_item->NextList = next_item;
  274.          }
  275.          first_item = cur_item;
  276.       }
  277. /*
  278.  *  When there's only one list left, traverse the list, setting the
  279.  *  reverse pointers so that the list is properly linked both directions.
  280.  */
  281.       first_item->NextList = NULL;
  282.       while (cur_item->Next != NULL)
  283.       {
  284.          cur_item->Next->NextList = cur_item;
  285.          cur_item = cur_item->Next;
  286.       }
  287.    }
  288.    return(first_item);
  289. }
  290.